package 蓝桥杯_2013;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 标题:连号区间数
 * 小明这些天一直在思考这样一个奇怪而有趣的问题:
 * 在1-N的某个全排列中有多少个连号区间呢?这里所说的连号区间的定义是:
 * 如果区间[L,R]里的所有元素(即此排列的第L个到第R个元素)递增排序后能得到一个长度为R-L+1的“连续”数列,则称这个区间连号区间
 * 当N很小的时候,小明可以很快地算出答案,但是当变大的时候,问题就不是那么简单了,现在小明需要你的帮助。
 * 输入格式:
 * 第一行是一个正整数N(1<=N<=50000),表示全排列的规模
 * 第二行是N个不同的数字Pi(1<=Pi<=N),表示这N个数字的某一全排列
 * 输出格式
 * 输出一个整数,表不同连号区间的数目
 * <p>
 * 示例
 * 用户输入:
 * 4
 * 3241
 * 程序应输出:
 * 7
 * 用户输入:
 * 5
 * 34251
 * 程序应输出:
 * 9
 */
public class Test08_连号区间数 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        // 方法一
        int N = input.nextInt();    // 输入规模
        String strs = input.next(); // 输入某一排列
        String str = null;          // 存储截取的字符串
        for (int i = 0; i < strs.length(); i++) {
            for (int j = i; j < strs.length(); j++) {
                // 截取
                str = strs.substring(i,j+1);
                // 转成字符串数组
                char[] chars = str.toCharArray();
                // 转成int型数组
                List<Integer> list = new ArrayList();
                for (char c:chars){
                    list.add(Integer.parseInt(String.valueOf(c)));
                }
                // 获取最大最小
                int min = list.get(0);
                int max = list.get(0);
                for (int k = 0; k < list.size() ; k++) {
                    if (list.get(k)<min){
                        min = list.get(k);
                    }
                    if (list.get(k)>max){
                        max = list.get(k);
                    }
                }
                // 判断：递增排序后能得到一个长度为R-L+1的“连续”数列
                // 长度 = R-L+1
                // 字符串截取的长度 = 最大-最小+1
                if ((j-i+1)==(max-min+1)){
                    System.out.println((i+1)+" "+(j+1));
                }
            }
        }

//        int n = input.nextInt();
//        int[] arr = new int[n+1];
//        for (int i = 1; i < arr.length; i++) {
//            arr[i] = input.nextInt();
//        }


    }
}
